package com.peng.eor;

import org.junit.Test;

public class EorTest {


    /**
     * 假设给定一个数组，但需要指定限定内部的数据规模：
     * 只有一种数出现了K次，另外一种数出现了M次，且K<M
     * 请问这个出现K次的数是多少？
     */
    @Test
    public void eorTest() {

        int[] arr = {1, 3, 3, 2, 1, 1, 1, 2, 2, 2};

        int num = getKNum(arr, 2, 4);

        System.out.println(num);

    }

    /**
     * 假设给定一个数组，但需要指定限定内部的数据规模：
     * 只有一种数出现了K次，另外一种数出现了M次，且K<M
     * 请问这个出现K次的数是多少？
     * 要求：空间复杂度O（1），时间复杂度O（N)
     *
     * @param arr 目标数组
     * @param k 只有一种数出现了K次
     * @param m 其他数都出现了M次
     * @return 出现了K次的数是啥？
     */
    private int getKNum(int[] arr, int k, int m) {
        /*
        在java中，一个int类型的数字占用32个
        用这个结构来记录32位上的每一位上，关于arr每个数关于这一位上的累加和
         */
        int[] countArr = new int[32];

        /*
        每个数都可以表示成一个32位的二进制形式，在32位上每一位可能是0，可能是1
        我们把每一个数的位上的位数累加到对应的第几位上去
         */
        for (int i : arr) {
            for (int j = 0; j < countArr.length; j++) {
                /*
                (i >> j) & 1 是啥意思？
                是为了得到当前数字i，在二进制第j位上的位数是啥
                举例：
                数字i=2，二进制为：0010，
                step01：
                i >> 0 = 0010
                  &
                  1      0001   =   0000，得到的就是数字i（i=2）第0位上的位数为0
                step02：
                i >> 1 = 0001
                  &
                  1      0001   =   000·，得到的就是数字i（i=2）第1位上的位数为1


                  最终把所有数字的位数值都累加到countArr对应的位上去
                 */
                countArr[j] += (i >> j) & 1;

            }
        }
        /*

        通过上述流程，我们得到了一个基于所有数的，每一位上的位值和，可这有什么用？
        假设K=2，M=6，如果基于上面的累加，关于countArr[i] % M 得到的值：
        如果是0，那么说明在此累加的都是出现M次的数种
        如果!=0，那么说明在此累加的，是含有K次种类的数的，即K次种类的数在此位上的位值一定为1！

        基于以上规律，
        我们准备一个结果值，
        我们只需要把countArr每一个countArr[i] % M！=0的对应位，将其设置到结果值的这一位上置为1，最终复现的就是出现K次的数
         */

        int res = 0;
        for (int i = 0; i < countArr.length; i++) {
            if (countArr[i] % m != 0) {
                res |= 1<<i;
            }

        }

        return res;


    }
}
